{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第四题：实现预剪枝"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实验内容\n",
    "1. 实现使用信息增益率划分的预剪枝\n",
    "2. 计算出带有预剪枝和不带预剪枝的决策树的精度，查准率，查全率和F1值(最大深度为6，使用信息增益率)，保留4位小数，四舍五入"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们会以“信息增益率(information gain ratio)”作为划分准则，构造带有预剪枝的二叉决策树  \n",
    "使用的数据和第三题一样，剪枝需要使用验证集，所以数据划分策略会和第三题不同"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 读取数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 导入类库\n",
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 导入数据\n",
    "loans = pd.read_csv('data/lendingclub/lending-club-data.csv', low_memory=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 对数据进行预处理，将safe_loans作为标记\n",
    "loans['safe_loans'] = loans['bad_loans'].apply(lambda x : +1 if x==0 else -1)\n",
    "del loans['bad_loans']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "features = ['grade',              # grade of the loan\n",
    "            'term',               # the term of the loan\n",
    "            'home_ownership',     # home_ownership status: own, mortgage or rent\n",
    "            'emp_length',         # number of years of employment\n",
    "           ]\n",
    "target = 'safe_loans'\n",
    "loans = loans[features + [target]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 划分训练集和测试集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.utils import shuffle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "loans = shuffle(loans, random_state = 34)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**我们使用数据的60%做训练集，20%做验证集，20%做测试集**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "split_line1 = int(len(loans) * 0.6)\n",
    "split_line2 = int(len(loans) * 0.8)\n",
    "train_data = loans.iloc[: split_line1]\n",
    "validation_data = loans.iloc[split_line1: split_line2]\n",
    "test_data = loans.iloc[split_line2:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 特征预处理"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def one_hot_encoding(data, features_categorical):\n",
    "    '''\n",
    "    Parameter\n",
    "    ----------\n",
    "    data: pd.DataFrame\n",
    "    \n",
    "    features_categorical: list(str)\n",
    "    '''\n",
    "    \n",
    "    # 对所有的离散特征遍历\n",
    "    for cat in features_categorical:\n",
    "        \n",
    "        # 对这列进行one-hot编码，前缀为这个变量名\n",
    "        one_encoding = pd.get_dummies(data[cat], prefix = cat)\n",
    "        \n",
    "        # 将生成的one-hot编码与之前的dataframe拼接起来\n",
    "        data = pd.concat([data, one_encoding],axis=1)\n",
    "        \n",
    "        # 删除掉原始的这列离散特征\n",
    "        del data[cat]\n",
    "    \n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_data = one_hot_encoding(train_data, features)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "one_hot_features = train_data.columns.tolist()\n",
    "one_hot_features.remove(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "validation_tmp = one_hot_encoding(validation_data, features)\n",
    "validation_data = pd.DataFrame(columns = train_data.columns)\n",
    "for feature in train_data.columns:\n",
    "    if feature in validation_tmp:\n",
    "        validation_data[feature] = validation_tmp[feature].copy()\n",
    "    else:\n",
    "        validation_data[feature] = np.zeros(len(validation_tmp), dtype = 'uint8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_data_tmp = one_hot_encoding(test_data, features)\n",
    "test_data = pd.DataFrame(columns = train_data.columns)\n",
    "for feature in train_data.columns:\n",
    "    if feature in test_data_tmp.columns:\n",
    "        test_data[feature] = test_data_tmp[feature].copy()\n",
    "    else:\n",
    "        test_data[feature] = np.zeros(test_data_tmp.shape[0], dtype = 'uint8')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "打印一下3个数据集的shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(train_data.shape, validation_data.shape, test_data.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. 实现信息增益率的计算\n",
    "信息熵：\n",
    "$$\n",
    "\\mathrm{Ent}(D) = - \\sum^{\\vert \\mathcal{Y} \\vert}_{k = 1} p_k \\mathrm{log}_2 p_k\n",
    "$$\n",
    "\n",
    "信息增益：\n",
    "$$\n",
    "\\mathrm{Gain}(D, a) = \\mathrm{Ent}(D) - \\sum^{V}_{v=1} \\frac{\\vert D^v \\vert}{\\vert D \\vert} \\mathrm{Ent}(D^v)\n",
    "$$\n",
    "\n",
    "信息增益率：\n",
    "\n",
    "$$\n",
    "\\mathrm{Gain\\_ratio}(D, a) = \\frac{\\mathrm{Gain}(D, a)}{\\mathrm{IV}(a)}\n",
    "$$\n",
    "\n",
    "其中\n",
    "\n",
    "$$\n",
    "\\mathrm{IV}(a) = - \\sum^V_{v=1} \\frac{\\vert D^v \\vert}{\\vert D \\vert} \\log_2 \\frac{\\vert D^v \\vert}{\\vert D \\vert}\n",
    "$$\n",
    "\n",
    "计算信息熵时约定：若$p = 0$，则$p \\log_2p = 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先实现信息熵，再实现信息增益率"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def information_entropy(labels_in_node):\n",
    "    '''\n",
    "    求当前结点的信息熵\n",
    "    \n",
    "    Parameter\n",
    "    ----------\n",
    "    labels_in_node: np.ndarray, 如[-1, 1, -1, 1, 1]\n",
    "    \n",
    "    Returns\n",
    "    ----------\n",
    "    float: information entropy\n",
    "    '''\n",
    "    \n",
    "    # 统计样本总个数\n",
    "    num_of_samples = labels_in_node.shape[0]\n",
    "    \n",
    "    if num_of_samples == 0:\n",
    "        return 0\n",
    "    \n",
    "    # 统计出标记为1的个数\n",
    "    num_of_positive = len(labels_in_node[labels_in_node == 1])\n",
    "    \n",
    "    # 统计出标记为-1的个数\n",
    "    num_of_negative =                                                            # YOUR CODE HERE\n",
    "    \n",
    "    # 统计正例的概率\n",
    "    prob_positive = num_of_positive / num_of_samples\n",
    "    \n",
    "    # 统计负例的概率\n",
    "    prob_negative =                                                              # YOUR CODE HERE\n",
    "    \n",
    "    if prob_positive == 0:\n",
    "        positive_part = 0\n",
    "    else:\n",
    "        positive_part = prob_positive * np.log2(prob_positive)\n",
    "    \n",
    "    if prob_negative == 0:\n",
    "        negative_part = 0\n",
    "    else:\n",
    "        negative_part = prob_negative * np.log2(prob_negative)\n",
    "    \n",
    "    return - ( positive_part + negative_part )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 信息熵测试样例1\n",
    "example_labels = np.array([-1, -1, 1, 1, 1])\n",
    "print(information_entropy(example_labels)) # 0.97095\n",
    "\n",
    "# 信息熵测试样例2\n",
    "example_labels = np.array([-1, -1, 1, 1, 1, 1, 1])\n",
    "print(information_entropy(example_labels)) # 0.86312\n",
    "    \n",
    "# 信息熵测试样例3\n",
    "example_labels = np.array([-1, -1, -1, -1, -1, 1, 1])\n",
    "print(information_entropy(example_labels)) # 0.86312\n",
    "\n",
    "# 信息熵测试样例4\n",
    "example_labels = np.array([-1] * 9 + [1] * 8)\n",
    "print(information_entropy(example_labels)) # 0.99750\n",
    "\n",
    "# 信息熵测试样例5\n",
    "example_labels = np.array([1] * 8)\n",
    "print(information_entropy(example_labels)) # 0\n",
    "\n",
    "# 信息熵测试样例6\n",
    "example_labels = np.array([])\n",
    "print(information_entropy(example_labels)) # 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_information_gain_ratios(data, features, target, annotate = False):\n",
    "    '''\n",
    "    计算所有特征的信息增益率并保存起来\n",
    "    \n",
    "    Parameter\n",
    "    ----------\n",
    "    data: pd.DataFrame, 带有特征和标记的数据\n",
    "    \n",
    "    features: list(str)，特征名组成的list\n",
    "    \n",
    "    target: str， 特征的名字\n",
    "    \n",
    "    annotate: boolean, default False，是否打印注释\n",
    "    \n",
    "    Returns\n",
    "    ----------\n",
    "    gain_ratios: dict, key: str, 特征名\n",
    "                       value: float，信息增益率\n",
    "    '''\n",
    "    \n",
    "    gain_ratios = dict()\n",
    "    \n",
    "    # 对所有的特征进行遍历，使用当前的划分方法对每个特征进行计算\n",
    "    for feature in features:\n",
    "        \n",
    "        # 左子树保证所有的样本的这个特征取值为0\n",
    "        left_split_target = data[data[feature] == 0][target]\n",
    "        \n",
    "        # 右子树保证所有的样本的这个特征取值为1\n",
    "        right_split_target =  data[data[feature] == 1][target]\n",
    "            \n",
    "        # 计算左子树的信息熵\n",
    "        left_entropy = information_entropy(left_split_target)\n",
    "        \n",
    "        # 计算左子树的权重\n",
    "        left_weight = len(left_split_target) / (len(left_split_target) + len(right_split_target))\n",
    "\n",
    "        # 计算右子树的信息熵\n",
    "        right_entropy = information_entropy(right_split_target)\n",
    "        \n",
    "        # 计算右子树的权重\n",
    "        right_weight = len(right_split_target) / (len(left_split_target) + len(right_split_target))\n",
    "        \n",
    "        # 计算当前结点的信息熵\n",
    "        current_entropy = information_entropy(data[target])\n",
    "        \n",
    "        # 计算当前结点的信息增益\n",
    "        gain =                                                                                       # YOUR CODE HERE\n",
    "        \n",
    "        # 计算IV公式中，当前特征为0的值\n",
    "        if left_weight == 0:\n",
    "            left_IV = 0\n",
    "        else:\n",
    "            left_IV =                                                                                # YOUR CODE HERE\n",
    "        \n",
    "        # 计算IV公式中，当前特征为1的值\n",
    "        if right_weight == 0:\n",
    "            right_IV = 0\n",
    "        else:\n",
    "            right_IV =                                                                               # YOUR CODE HERE\n",
    "        \n",
    "        # IV 等于所有子树IV之和的相反数\n",
    "        IV = - (left_IV + right_IV)\n",
    "            \n",
    "        # 计算使用当前特征划分的信息增益率\n",
    "        # 这里为了防止IV是0，导致除法得到np.inf，在分母加了一个很小的小数\n",
    "        gain_ratio = gain / (IV + np.finfo(np.longdouble).eps)\n",
    "        \n",
    "        # 信息增益率的存储\n",
    "        gain_ratios[feature] = gain_ratio\n",
    "        \n",
    "        if annotate:\n",
    "            print(\" \", feature, gain_ratio)\n",
    "            \n",
    "    return gain_ratios"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 信息增益率测试样例1\n",
    "print(compute_information_gain_ratios(train_data, one_hot_features, target)['grade_A']) # 0.02573\n",
    "\n",
    "# 信息增益率测试样例2\n",
    "print(compute_information_gain_ratios(train_data, one_hot_features, target)['grade_B']) # 0.00418\n",
    "\n",
    "# 信息增益率测试样例3\n",
    "print(compute_information_gain_ratios(train_data, one_hot_features, target)['term_ 60 months']) # 0.01971"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. 完成最优特征的选择 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里我们没有实现信息增益和基尼指数的最优特征求解，感兴趣的同学可以按上一题实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def best_splitting_feature(data, features, target, criterion = 'gain_ratios', annotate = False):\n",
    "    '''\n",
    "    给定划分方法和数据，找到最优的划分特征\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    data: pd.DataFrame, 带有特征和标记的数据\n",
    "    \n",
    "    features: list(str)，特征名组成的list\n",
    "    \n",
    "    target: str， 特征的名字\n",
    "    \n",
    "    criterion: str, 使用哪种指标，三种选项: 'information_gain', 'gain_ratio', 'gini'\n",
    "    \n",
    "    annotate: boolean, default False，是否打印注释\n",
    "    \n",
    "    Returns\n",
    "    ----------\n",
    "    best_feature: str, 最佳的划分特征的名字\n",
    "    \n",
    "    '''\n",
    "    if criterion == 'information_gain':\n",
    "        if annotate:\n",
    "            print('using information gain')\n",
    "        return None\n",
    "\n",
    "    elif criterion == 'gain_ratio':\n",
    "        if annotate:\n",
    "            print('using information gain ratio')\n",
    "        \n",
    "        # 得到当前所有特征的信息增益率\n",
    "        gain_ratios = compute_information_gain_ratios(data, features, target, annotate)\n",
    "    \n",
    "        # 根据这些特征和他们的信息增益率，找到最佳的划分特征\n",
    "        best_feature = max(gain_ratios.items(), key = lambda x: x[1])[0]\n",
    "\n",
    "        return best_feature\n",
    "    \n",
    "    elif criterion == 'gini':\n",
    "        if annotate:\n",
    "            print('using gini')\n",
    "        return None\n",
    "    else:\n",
    "        raise Exception(\"传入的criterion不合规!\", criterion)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. 判断结点内样本的类别是否为同一类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intermediate_node_num_mistakes(labels_in_node):\n",
    "    '''\n",
    "    求树的结点中，样本数少的那个类的样本有多少，比如输入是[1, 1, -1, -1, 1]，返回2\n",
    "    \n",
    "    Parameter\n",
    "    ----------\n",
    "    labels_in_node: np.ndarray, pd.Series\n",
    "    \n",
    "    Returns\n",
    "    ----------\n",
    "    int：个数\n",
    "    \n",
    "    '''\n",
    "    # 如果传入的array为空，返回0\n",
    "    if len(labels_in_node) == 0:\n",
    "        return 0\n",
    "    \n",
    "    # 统计1的个数\n",
    "    num_of_one =                                                               # YOUR CODE HERE\n",
    "    \n",
    "    # 统计-1的个数\n",
    "    num_of_minus_one =                                                         # YOUR CODE HERE\n",
    "    \n",
    "    return num_of_one if num_of_minus_one > num_of_one else num_of_minus_one"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7. 创建叶子结点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先编写一个辅助函数majority_class，求树的结点中，样本数多的那个类是什么"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def majority_class(labels_in_node):\n",
    "    '''\n",
    "        求树的结点中，样本数多的那个类是什么\n",
    "    '''\n",
    "    # 如果传入的array为空，返回0\n",
    "    if len(labels_in_node) == 0:\n",
    "        return 0\n",
    "    \n",
    "    # 统计1的个数\n",
    "    num_of_one =                                                               # YOUR CODE HERE\n",
    "    \n",
    "    # 统计-1的个数\n",
    "    num_of_minus_one =                                                         # YOUR CODE HERE\n",
    "    \n",
    "    return 1 if num_of_minus_one < num_of_one else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_leaf(target_values):\n",
    "    '''\n",
    "    计算出当前叶子结点的标记是什么，并且将叶子结点信息保存在一个dict中\n",
    "    \n",
    "    Parameter:\n",
    "    ----------\n",
    "    target_values: pd.Series, 当前叶子结点内样本的标记\n",
    "\n",
    "    Returns:\n",
    "    ----------\n",
    "    leaf: dict，表示一个叶结点，\n",
    "            leaf['splitting_features'], None，叶结点不需要划分特征\n",
    "            leaf['left'], None，叶结点没有左子树\n",
    "            leaf['right'], None，叶结点没有右子树\n",
    "            leaf['is_leaf'], True, 是否是叶子结点\n",
    "            leaf['prediction'], int, 表示该叶子结点的预测值\n",
    "    '''\n",
    "    # 创建叶子结点\n",
    "    leaf = {'splitting_feature' : None,\n",
    "            'left' : None,\n",
    "            'right' : None,\n",
    "            'is_leaf': True}\n",
    "   \n",
    "    # 数结点内-1和+1的个数\n",
    "    num_ones = len(target_values[target_values == +1])\n",
    "    num_minus_ones = len(target_values[target_values == -1])    \n",
    "\n",
    "    # 叶子结点的标记使用少数服从多数的原则，为样本数多的那类的标记，保存在 leaf['prediction']\n",
    "    leaf['prediction'] = majority_class(target_values)\n",
    "\n",
    "    # 返回叶子结点\n",
    "    return leaf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8. 递归地创建决策树\n",
    "递归的创建决策树  \n",
    "决策树终止的三个条件：\n",
    "1. 如果结点内所有的样本的标记都相同，该结点就不需要再继续划分，直接做叶子结点即可\n",
    "2. 如果结点所有的特征都已经在之前使用过了，在当前结点无剩余特征可供划分样本，该结点直接做叶子结点\n",
    "3. 如果当前结点的深度已经达到了我们限制的树的最大深度，直接做叶子结点\n",
    "\n",
    "对于预剪枝来说，实质上是增加了第四个终止条件：  \n",
    "4. 如果当前结点划分后，模型的泛化能力没有提升，则不进行划分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如何判断泛化能力有没有提升？我们需要使用验证集  \n",
    "就像使用训练集递归地划分数据一样，我们在递归地构造决策树时，也需要递归地将验证集进行划分，计算决策树在验证集上的精度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因为我们是递归地对决策树进行划分，所以每次计算验证集上精度是否提升时，也只是针对当前结点内的样本，因为是否对当前结点内的样本进行划分，不会影响它的兄弟结点及兄弟结点的子结点的精度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**需要完成11个部分**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decision_tree_create(training_data, validation_data, features, target, criterion = 'gain_ratios', pre_pruning = False, current_depth = 0, max_depth = 10, annotate = False):\n",
    "    '''\n",
    "    Parameter:\n",
    "    ----------\n",
    "    trianing_data: pd.DataFrame, 数据\n",
    "\n",
    "    features: iterable, 特征组成的可迭代对象\n",
    "\n",
    "    target: str, 标记的名字\n",
    "\n",
    "    criterion: 'str', 特征划分方法\n",
    "\n",
    "    current_depth: int, 当前深度\n",
    "\n",
    "    max_depth: int, 树的最大深度\n",
    "\n",
    "    Returns:\n",
    "    ----------\n",
    "    dict, dict['is_leaf']          : False, 当前顶点不是叶子结点\n",
    "          dict['prediction']       : None, 不是叶子结点就没有预测值\n",
    "          dict['splitting_feature']: splitting_feature, 当前结点是使用哪个特征进行划分的\n",
    "          dict['left']             : dict\n",
    "          dict['right']            : dict\n",
    "    '''\n",
    "    if criterion not in ['information_gain', 'gain_ratio', 'gini']:\n",
    "        raise Exception(\"传入的criterion不合规!\", criterion)\n",
    "    \n",
    "    # 复制一份特征，存储起来，每使用一个特征进行划分，我们就删除一个\n",
    "    remaining_features = features[:]\n",
    "    \n",
    "    # 取出标记值\n",
    "    target_values = training_data[target]\n",
    "    validation_values = validation_data[target]\n",
    "    print(\"-\" * 50)\n",
    "    print(\"Subtree, depth = %s (%s data points).\" % (current_depth, len(target_values)))\n",
    "\n",
    "    # 终止条件1\n",
    "    # 如果当前结点内所有样本同属一类，即这个结点中，各类别样本数最小的那个等于0\n",
    "    # 使用前面写的intermediate_node_num_mistakes来完成这个判断\n",
    "    if                                                                                        # YOUR CODE HERE\n",
    "        print(\"Stopping condition 1 reached.\")\n",
    "        return create_leaf(target_values)   # 创建叶子结点\n",
    "    \n",
    "    # 终止条件2\n",
    "    # 如果已经没有剩余的特征可供分割\n",
    "    if                                                                                        # YOUR CODE HERE\n",
    "        print(\"Stopping condition 2 reached.\")\n",
    "        return create_leaf(target_values)   # 创建叶子结点\n",
    "    \n",
    "    # 终止条件3\n",
    "    # 如果已经到达了我们要求的最大深度\n",
    "    if                                                                                        # YOUR CODE HERE\n",
    "        print(\"Reached maximum depth. Stopping for now.\")\n",
    "        return create_leaf(target_values)   # 创建叶子结点\n",
    "    \n",
    "    # 找到最优划分特征\n",
    "    # 使用best_splitting_feature这个函数\n",
    "    splitting_feature =                                                                       # YOUR CODE HERE\n",
    "    \n",
    "    # 使用我们找到的最优特征将数据划分成两份\n",
    "    # 左子树的数据\n",
    "    left_split = training_data[training_data[splitting_feature] == 0]\n",
    "    \n",
    "    # 右子树的数据\n",
    "    right_split =                                                                             # YOUR CODE HERE\n",
    "    \n",
    "    # 使用这个最优特征对验证集进行划分\n",
    "    validation_left_split = validation_data[validation_data[splitting_feature] == 0]\n",
    "    validation_right_split = validation_data[validation_data[splitting_feature] == 1]\n",
    "    \n",
    "    # 如果使用预剪枝，需要判断在验证集上的精度是否提升了\n",
    "    if pre_pruning:\n",
    "        # 首先计算不划分的时候的在验证集上的精度，也就是当前结点为叶子结点\n",
    "        # 统计当前结点样本中，样本数多的那个类(majority class)\n",
    "        true_class =                                                                          # YOUR CODE HERE\n",
    "\n",
    "        # 判断验证集在不划分时的精度，分母加eps是因为，有可能在划分的时候，验证集的样本数为0\n",
    "        acc_without_splitting = len(validation_values[validation_values == true_class]) / (len(validation_values) + np.finfo(np.longdouble).eps)\n",
    "\n",
    "        # 对当前结点进行划分，统计划分后，左子树的majority class\n",
    "        left_true_class = majority_class(left_split[target])\n",
    "\n",
    "        # 对当前结点进行划分，统计右子树的majority class\n",
    "        right_true_class =                                                                    # YOUR CODE HERE\n",
    "\n",
    "        # 统计验证集左子树中有多少样本是左子树的majority class\n",
    "        vali_left_num_of_majority = len(validation_left_split[validation_left_split[target] == left_true_class])\n",
    "\n",
    "        # 统计验证集右子树中有多少样本是右子树的majority class\n",
    "        vali_right_num_of_majority =                                                          # YOUR CODE HERE\n",
    "\n",
    "        # 计算划分后的精度\n",
    "        acc_with_splitting = (vali_left_num_of_majority + vali_right_num_of_majority) / (len(validation_data) + np.finfo(np.longdouble).eps)\n",
    "\n",
    "        if annotate == True:\n",
    "            print('acc before splitting: %.3f'%(acc_without_splitting))\n",
    "            print('acc after splitting: %.3f'%(acc_with_splitting))\n",
    "\n",
    "        # 如果划分后的精度小于等于划分前的精度，那就不划分，当前结点直接变成叶子结点\n",
    "        # 否则继续划分，创建左右子树\n",
    "        if acc_with_splitting < acc_without_splitting:\n",
    "            print('Pre-Pruning')\n",
    "            # 创建叶子结点\n",
    "            return                                                                            # YOUR CODE HERE\n",
    "    \n",
    "    # 从剩余特征中删除掉当前这个特征\n",
    "    remaining_features.remove(splitting_feature)\n",
    "    \n",
    "    print(\"Split on feature %s. (%s, %s)\" % (\\\n",
    "                      splitting_feature, len(left_split), len(right_split)))\n",
    "    \n",
    "    # 如果使用当前的特征，将所有的样本都划分到一棵子树中，那么就直接将这棵子树变成叶子结点\n",
    "    # 判断左子树是不是“完美”的\n",
    "    if len(left_split) == len(training_data):\n",
    "        print(\"Creating leaf node.\")\n",
    "        return create_leaf(left_split[target])\n",
    "    \n",
    "    # 判断右子树是不是“完美”的\n",
    "    if len(right_split) == len(training_data):\n",
    "        print(\"Creating right node.\")\n",
    "        return                                                                                # YOUR CODE HERE\n",
    "\n",
    "    # 递归地创建左子树，需要传入验证集的左子树\n",
    "    left_tree = decision_tree_create(left_split, validation_left_split, remaining_features, target, criterion, pre_pruning, current_depth + 1, max_depth, annotate)\n",
    "    \n",
    "    # 递归地创建右子树，需要传入验证集的右子树\n",
    "    \n",
    "    right_tree =                                                                              # YOUR CODE HERE\n",
    "\n",
    "    return {'is_leaf'          : False, \n",
    "            'prediction'       : None,\n",
    "            'splitting_feature': splitting_feature,\n",
    "            'left'             : left_tree, \n",
    "            'right'            : right_tree}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "训练一棵没有预剪枝的决策树，最大深度为6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_without_pre_pruning = decision_tree_create(train_data, validation_data, one_hot_features, target, criterion = 'gain_ratio', pre_pruning = False, current_depth = 0, max_depth = 6, annotate = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "训练一棵有预剪枝的决策树，最大深度为6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_with_pre_pruning = decision_tree_create(train_data, validation_data, one_hot_features, target, criterion = \"gain_ratio\", pre_pruning = True, current_depth = 0, max_depth = 6, annotate = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 9. 预测"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classify(tree, x, annotate = False):\n",
    "    '''\n",
    "    递归的进行预测，一次只能预测一个样本\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    tree: dict\n",
    "    \n",
    "    x: pd.Series，样本\n",
    "    \n",
    "    x: pd.DataFrame, 待预测的样本\n",
    "    \n",
    "    annotate, boolean, 是否显示注释\n",
    "    \n",
    "    Returns\n",
    "    ----------\n",
    "    返回预测的标记\n",
    "    '''\n",
    "    if tree['is_leaf']:\n",
    "        if annotate:\n",
    "            print (\"At leaf, predicting %s\" % tree['prediction'])\n",
    "        return tree['prediction']\n",
    "    else:\n",
    "        split_feature_value = x[tree['splitting_feature']]\n",
    "        if annotate:\n",
    "             print (\"Split on %s = %s\" % (tree['splitting_feature'], split_feature_value))\n",
    "        if split_feature_value == 0:\n",
    "            return classify(tree['left'], x, annotate)\n",
    "        else:\n",
    "            return classify(tree['right'], x, annotate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict(tree, data):\n",
    "    '''\n",
    "    按行遍历data，对每个样本进行预测，将值存储起来，最后返回np.ndarray\n",
    "    \n",
    "    Parameter\n",
    "    ----------\n",
    "    tree, dict, 模型\n",
    "    \n",
    "    data, pd.DataFrame, 数据\n",
    "    \n",
    "    Returns\n",
    "    ----------\n",
    "    predictions, np.ndarray, 模型对这些样本的预测结果\n",
    "    '''\n",
    "    predictions = np.zeros(len(data))\n",
    "    \n",
    "    # YOUR CODE HERE\n",
    "    for i in range(len(data)):\n",
    "        predictions[i] = classify(tree, data.iloc[i])\n",
    "    \n",
    "    return predictions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 在下方计算出带有预剪枝和不带预剪枝的决策树的精度，查准率，查全率和F1值(最大深度为6，使用信息增益率)，保留4位小数，四舍五入"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 双击此处编辑\n",
    "\n",
    "模型|精度|查准率|查全率|F1\n",
    "-|-|-|-|-\n",
    "有预剪枝| 0.0 | 0.0 | 0.0 | 0.0\n",
    "无预剪枝| 0.0 | 0.0 | 0.0 | 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 10. 可视化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyecharts import Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_echarts_data(tree):\n",
    "    \n",
    "    # 当前顶点的dict\n",
    "    value = dict()\n",
    "    \n",
    "    # 如果传入的tree已经是叶子结点了\n",
    "    if tree['is_leaf'] == True:\n",
    "        \n",
    "        # 它的value就设置为预测的标记\n",
    "        value['value'] = tree['prediction']\n",
    "        \n",
    "        # 它的名字就叫\"label: 标记\"\n",
    "        value['name'] = 'label: %s'%(tree['prediction'])\n",
    "        \n",
    "        # 直接返回这个dict即可\n",
    "        return value\n",
    "    \n",
    "    # 如果传入的tree不是叶子结点，名字就叫当前这个顶点的划分特征，子树是一个list\n",
    "    # 分别增加左子树和右子树到children中\n",
    "    value['name'] = tree['splitting_feature']\n",
    "    value['children'] = [generate_echarts_data(tree['left']), generate_echarts_data(tree['right'])]\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data1 = generate_echarts_data(tree_without_pre_pruning)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = Tree(width=800, height=800)\n",
    "tree.add(\"\",\n",
    "         [data1],\n",
    "         tree_collapse_interval=5,\n",
    "         tree_top=\"15%\",\n",
    "         tree_right=\"20%\",\n",
    "         tree_symbol = 'rect',\n",
    "         tree_symbol_size = 20,\n",
    "         )\n",
    "tree.render()\n",
    "tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data2 = generate_echarts_data(tree_with_pre_pruning)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = Tree(width=800, height=800)\n",
    "tree.add(\"\",\n",
    "         [data2],\n",
    "         tree_collapse_interval=5,\n",
    "         tree_top=\"15%\",\n",
    "         tree_right=\"20%\",\n",
    "         tree_symbol = 'rect',\n",
    "         tree_symbol_size = 20,\n",
    "         )\n",
    "tree.render()\n",
    "tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
